// 回答：动态规划算法
function maxSubArray(nums) {
    let currentSum = nums[0]; // 当前子数组和初始化为第一个元素
    let maxSum = nums[0]; // 全局最大子数组和也初始化为第一个元素

    // 从数组的第二个元素开始遍历
    for (let i = 1; i < nums.length; i++) {
        // 在每个位置上，考虑两种情况：
        // 1. 将当前元素加入到当前的和中，使得当前和增大。
        // 2. 从当前元素重新开始计算当前的和，因为当前元素本身已经比当前的和更大。
        currentSum = Math.max(nums[i], currentSum + nums[i]);
        
        // 更新全局最大和
        maxSum = Math.max(maxSum, currentSum);
    }

    return maxSum;
}

// 测试
const nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4];
console.log("最大子数组和为:", maxSubArray(nums)); // 输出: 6，对应子数组为 [4, -1, 2, 1]

// 动态规划的优势在于它可以将复杂问题分解成更小的子问题，然后通过求解子问题来得到最终的解
